package org.example.everyday;

import sun.misc.SoftCache;

import java.lang.reflect.Parameter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <p>
 * Description:https://leetcode-cn.com/problems/number-of-ways-to-reconstruct-a-tree/
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/2/16 10:28
 */
public class Lc1719 {
    public static void main(String[] args) {
        Lc1719 lc1719 = new Lc1719();
//        int[][] nums = new int[][]{{1,2},{2,3},{1,3}};
        //不满足条件的数组
//        int[][] nums = new int[][]{{1,2},{2,3},{2,4},{1,5}};

//        int[][] nums = new int[][]{{1,2},{2,3}};

        int[][] nums = {{1,5},{3,4},{3,5},{4,5},{2,5},{1,3},{1,4}};

        int result = lc1719.checkWays(nums);
        System.out.println(result);
    }


    public int checkWays(int[][] pairs) {
       Map<Integer,Set<Integer>> adj = new HashMap<>();
       for(int[] pair : pairs){
           adj.putIfAbsent(pair[0],new HashSet<Integer>());
           adj.putIfAbsent(pair[1],new HashSet<Integer>());
           adj.get(pair[0]).add(pair[1]);
           adj.get(pair[1]).add(pair[0]);
       }

       int root = -1;
       Set<Map.Entry<Integer,Set<Integer>>> entries = adj.entrySet();

       for (Map.Entry<Integer,Set<Integer>> entry : entries){
           int node = entry.getKey();
           Set<Integer> neighbours = entry.getValue();
           if(neighbours.size() == adj.size() - 1){
               root = node;
           }
       }
       if(root == -1){
           return 0;
       }
       int ans = 1;
       for (Map.Entry<Integer,Set<Integer>> entry : entries){
           int node = entry.getKey();
           if(node == root){
               continue;
           }
           Set<Integer> neighbours = entry.getValue();
           int parent = -1;
           int parentDegree = Integer.MAX_VALUE;
           int currDegree = neighbours.size();
           for (Integer neighbour :neighbours){
               if(adj.get(neighbour).size() < parentDegree && adj.get(neighbour).size() >= currDegree){
                    parent = neighbour;
                    parentDegree = adj.get(neighbour).size();
               }
           }
           if(parent == -1){
               return 0;
           }

           for(Integer neighbour : neighbours){
               if(neighbour == parent){
                   continue;
               }
               if(!adj.get(parent).contains(neighbour)){
                   return 0;
               }
           }

           if(currDegree == parentDegree){
               ans = 2;
           }

       }
        return ans;
    }
}
